package com.salim.leetcode.$152;

public class MaximumProductSubarray {

    /**
     *      2   3  -2  4
     * 2    2
     * 3    6   3
     * -2 -12  -6  -2
     * 4  -48 -24  -8  4
     *
     * d[i][i] = nums[i]
     *
     * d[i][j] = d[i][j-1] * d[nums.length-1][j]
     *
     * 针对0 1 -1的优化
     * nums去掉1的结果 去掉成对的-1
     * 对0的计算直接跳过整行
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }
        int max = nums[0];
        int realLength = 0;
        int[][] d = new int[nums.length][nums.length];
        for(int i=0;i<nums.length;i++){
            if(nums[i]==1){
                continue;
            }
            //如果当前是-1 校验是否下一个值是-1 要去掉1的情况
            if(nums[i]==-1){
                int j = i+1;
                boolean jump = false;
                for(;j<nums.length;j++){
                    if(nums[j]==1){
                        continue;
                    }else if(nums[j]==-1){
                        jump = true;
                        break;
                    }else{
                        break;
                    }
                }
                if(jump){
                    i=j+1;
                    continue;
                }
            }
            d[i][i] = nums[i];
            max = Math.max(max,d[i][i]);
            realLength++;
        }

        for(int j=1;j<realLength;j++) {
            if(d[j][j]==0){
                continue;
            }
            for (int i = 0; i < j; i++) {
                d[i][j] = d[i][j - 1] * d[j][j];
                max = Math.max(max,d[i][j]);
            }
        }
        return max;
    }
}
